package engine.operators;

import its.util.RandomFactory;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import engine.BoaOperator;
import engine.BoaPopulation;
import engine.ObjectiveFunction;
import engine.Population;
import engine.individuals.Individual;

public class BoaReplaceWorstOperator<T extends Individual<?>> implements
		BoaOperator<T> {

	private ObjectiveFunction<T> objectiveFunction;


	/*
	 * (non-Javadoc)
	 * 
	 * @see engine.BoaOperator#apply(engine.BoaPopulation, java.util.List)
	 */
	public BoaReplaceWorstOperator(ObjectiveFunction<T> objectiveFunction) {

		this.objectiveFunction = objectiveFunction;
	}

	@Override
	public BoaPopulation<T> apply(BoaPopulation<T> population,
			List<Population<T>> populations) {

		// initialize variables

		Population<T> originalPopulation = populations.get(0);
		int N = originalPopulation.size();
		int M = population.size();
		int n = population.getChromosomeSize();

		int NM = N - M;

		// shuffle the individuals a little
		Collections.shuffle(originalPopulation.getIndividuals(), RandomFactory.getRandom());
		// for (i=0; i<N; i++)
		// {
		// j = random.nextInt(N);
		//
		// if (i!=j)
		// swapIndividuals(population,i,j);
		// };

		// separate worst M individuals by divide and conquer

		divideWorst(originalPopulation.getIndividuals(), 0, N - 1, N - M);
		
		// replace the worst M

		List<T> replacedIndividuals = new ArrayList<T>(originalPopulation.size());

		for (int i = 0; i < NM; i++) {
			replacedIndividuals.add(originalPopulation.getIndividuals().get(i));
		}
		for (int i = NM; i < N; i++) {
			replacedIndividuals.add(population.getIndividuals().get(i - NM));
		}

		BoaPopulation<T> replacedPopulation = new BoaPopulation<T>(
				replacedIndividuals, n);

		return replacedPopulation;
	}

	/**
	 * Do divide-and-conquer until the last M individuals (individuals [NM...N])
	 * are worse or equal than the rest (of totally N individuals)
	 * 
	 * @param individuals
	 * @param left
	 *          a pointer pointing to the left-most individual of the currently
	 *          processed part of the population
	 * @param right
	 *          a pointer pointing to the right-most individual of the currently
	 *          processed part of the population
	 * @param NM
	 *          size of the population minus the number of individuals to separate
	 *          (N-M)
	 */
	private void divideWorst(List<T> individuals, int left, int right, int NM) {

		int l = left;
		int r = right;

		double leftValue = objectiveFunction.compute(individuals.get(l));
		double rightValue = objectiveFunction.compute(individuals.get(r));
		double pivot = (leftValue + rightValue) / 2.0d;

		while (l <= r) {
			while (l < right
					&& (leftValue = objectiveFunction.compute(individuals.get(l))) > pivot) {
				++l;
			}

			while (r > left
					&& (rightValue = objectiveFunction.compute(individuals.get(r))) < pivot) {
				--r;
			}

			if (l <= r) {
				if (l != r) {
					individuals = swapIndividuals(individuals, l, r);
				}

				l++;
				r--;
			}
		}

		if ((l == NM) || (r == (NM - 1))) {
			return;
		}

		if ((r >= NM) && (left < r)) {
			divideWorst(individuals, left, r, NM);
		}

		if ((l < NM) && (l < right)) {
			divideWorst(individuals, l, right, NM);
		}
	}

	private List<T> swapIndividuals(List<T> individuals, int l, int r) {

		T individual1 = individuals.get(l);
		T individual2 = individuals.get(r);

		individuals.set(r, individual1);
		individuals.set(l, individual2);

		return individuals;
	}

	@Override
	public Population<T> apply(Population<T> population) {

		throw new UnsupportedOperationException(
				"Use engine.BoaOperator#apply(engine.BoaPopulation, java.util.List) instead.");
	}

}